\documentclass[a4paper,12pt,notitlepage]{article}
\usepackage{graphicx}
\usepackage{amsmath,amssymb,amsfonts,amsthm}
\usepackage[english]{babel}
\usepackage[left=3cm,right=2cm,top=2.5cm,bottom=2.5cm]{geometry}

\newtheorem*{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\title {Online Square Detection}

\author
{
	Dmitry Kosolobov\thanks{Ural Federal university}
}

\date{CSEdays 2014}

\begin{document}
\maketitle

A string $s$ is a \emph{square} if $s = xx$ for some nonempty string $x$. We say that a string contains a square if the string has a substring that is a square. Let $f$ be a positive function of integer domain. We say that an algorithm \emph{detects} squares in $O(f(n))$ time if for any integer $n$ and any string of length $n$, the algorithm decides whether the string contains a square in $O(f(n))$ operations. We say that an algorithm detects squares \emph{online} if the algorithm processes the input string sequentially from left to right and decides whether each prefix contains a square after reading the rightmost letter of that prefix.

In this paper we give an algorithm that online detects squares in $O(n\log n)$ time and linear space.
%One can easily show that on an alphabet of size two each string of length at least four has a square. A classical result of Thue \cite{Thue} states that on an alphabet of size three there are infinitely many strings without squares.
Let us point out some previous results on this problem.
%(for shortening, we estimate only a running time of algorithms discussed since they all use linear space).

Main and Lorentz \cite{MainLorentz} presented an algorithm that detects squares in $O(n\log n)$ time. For unordered alphabets, they proved an $\Omega(n\log n)$ lower bound, so their result is the best possible in this case. For ordered alphabets, Crochemore \cite{Crochemore} described an algorithm that detects squares in $O(n\log \sigma)$ time, where $\sigma$ is the size of alphabet.

The interest in algorithms for online square detection is initially motivated by problems in the artificial intelligence research (see~\cite{LeungPengTing}). Leung, Peng, and Ting \cite{LeungPengTing} obtained an online algorithm that detects squares in $O(n\log^2 n)$ time. Jansson and Peng \cite{JanssonPeng} found an online algorithm that detects squares in $O(n(\log n + \sigma))$ time, where $\sigma$ is the size of alphabet; for ordered alphabets, their algorithm requires $O(n\log n)$ time. The present paper is inspired by Shur's work \cite{Shur}. See \cite{KolpakovKucherov} for a further discussion.

The following theorem, which is our result, solves an open problem posed in \cite{JanssonPeng}.

\begin{theorem}
There exists an algorithm that detects squares online in $O(n\log n)$ time and linear space.
\end{theorem}

Our algorithm maintains the string $text$. Let $n$ denotes $|text|$. To detect squares, we use an auxiliary data structure that is called a \emph{catcher}. The catcher contains two integer variables $i$, $j$ such that $0 < i < j$ and $j - i + 1 \le n - j$. The catcher detects square suffixes with the leftmost position lying in $\overline{i,j}$, i.e., if for some $k\in \overline{i,j}$, $text[k..n]$ is a square, the catcher detects this square. The segment $\overline{i,j}$ is called the \emph{trap}.

Suppose $text[k..n] = xx$ for some nonempty string $x$ and $k\in \overline{i,j}$ (see~fig.~\ref{fig:square}). Since $j - i + 1 \le n - j$, we have $x = x'x''$ for some strings $x'$ and $x''$ such that $text[j{+}1..n] = x''x'x''$. Recall that a \emph{boundary} of a string is a proper suffix that is a prefix of this string.

\begin{lemma}[see appendix]
If $text[1..n{-}1]$ does not contain squares, then $x''$ is the longest boundary of $text[j{+}1..n]$. \label{MaxBoundary}
\end{lemma}

Let $t = j - i + 1$. To obtain the longest boundary of $text[j{+}1..n]$, the catcher maintains an integer array $b[j{+}1..n]$ (for convenience, we use indices $\overline{j{+}1,n}$) such that for any $k\in\overline{j{+}1,n}$, $b[k]$ is equal to the length of the longest boundary of $text[j{+}1..k]$. Further, the catcher contains a variable $s$ such that if $2b[n] + t \ge n - j$, $s$ equals the length of the longest suffix of $text[i..j]$ that is a suffix of $text[1..n{-}b[n]]$ and otherwise, $s$ equals zero. Thus by Lemma~\ref{MaxBoundary}, the catcher detects a square iff $2b[n] + s \ge n - j$.
\begin{figure}[htb]
\vspace*{-4mm}
\small \includegraphics[scale=0.55]{square}
\vskip-2mm
\caption{\small The square $xx$ that is a suffix with the leftmost position lying in $\overline{i,j}$; $j - i + 1 \le n - j$.}
\vskip-2mm
\label{fig:square}
\end{figure}

Let us describe how to compute $b$ and $s$. There is a well-known algorithm that efficiently calculates $b[n]$ (see \cite{Stringology}). Once $b[n]$ is found, we process $s$. If $b[n] \ne b[n{-}1] + 1$, we assign $s = 0$. Next, if $2b[n] + t \ge n - j$ and $s = 0$, we compute $s$ by a naive algorithm.

\begin{lemma}[see appendix]
The catcher requires $O(n - j)$ time and space. \label{CatcherTime}
\end{lemma}

\begin{proof}[Proof of Theorem]
Our algorithm maintains $O(\log n)$ catchers and traps of these catchers cover the string $text$. Let $k \in \overline{0,\lfloor\log n\rfloor{-}1}$ and $p$ be the maximal integer such that $(p{+}1) 2^k \le n$. We have one or two traps of the length $2^k$: the first trap is equal to $\overline{(p{-}1)2^k{+}1,p2^k}$ and if $p$ is even, we have another trap that is equal to $\overline{(p{-}2)2^k{+}1,(p{-}1)2^k}$. If $n$ has became a multiple of $2^k$ after extension of $text$, we add a new trap of the length $2^k$ and destroy two previous traps of the length $2^k$ if the new $p$ is odd and these traps exist. One can prove that the described system of traps covers $text$.

It is easy to see that if for some $k \in \overline{0,\lfloor\log n\rfloor{-}1}$, the described algorithm maintains a trap $\overline{i,j}$ of the length $2^k$, then $n - j < 3\cdot 2^k$. Hence from Lemma~\ref{CatcherTime} it follows that all catchers of the algorithm use $O(2\sum_{k=0}^{\lfloor\log n\rfloor{-}1} 3\cdot 2^k) = O(n)$ space. Since traps of the same length do not intersect, to maintain traps of the length $2^k$, we require, by Lemma~\ref{CatcherTime}, $O(3\cdot 2^k \cdot \frac{n}{2^k}) = O(n)$ time. Thus, the algorithm takes $O(n\log n)$ time.
\end{proof}


\begin{thebibliography}{99}
\bibitem[Cr86]{Crochemore} M. Crochemore. Transducers and repetitions, Theoretical Computer Science 45 (1986) 63--86.
\bibitem[CR02]{Stringology} M. Crochemore, W. Rytter. Jewels of Stringology, World Scientific Publ. (2002).
\bibitem[JP05]{JanssonPeng} J. Jansson, Z. Peng. Online and dynamic recognition of squarefree strings, MFCS (2005) 520--531.
\bibitem[LPT04]{LeungPengTing} H.F. Leung, Z. Peng, H. F. Ting. An efficient online algorithm for square detection, Computing and Combinatorics (2004) 432--439.
\bibitem[ML85]{MainLorentz} M.G. Main, R.J. Lorentz. Linear time recognition of squarefree strings, Combinatorial Algorithms on Words (1985) 271--278.
\bibitem[Sh14]{Shur} A.M. Shur. Generating square-free words efficiently, WORDS'2013 special issue of Theoret. Comput. Sci. (submitted, 2014).
\bibitem[KK99]{KolpakovKucherov} R. Kolpakov, G. Kucherov. Finding maximal repetitions in a word in linear time, FOCS 40 (1999) 596--604.
%\bibitem[Th1906]{Thue} Thue A. {\"U}ber unendliche Zeichenreihen // Norske Videnskabers Selskabs Skrifter, Mat.-Nat. Kl., 7, 1906 -- pp. 1-22.
\end{thebibliography}

\section*{Appendix}

\begin{proof}[Proof of Lemma~\ref{MaxBoundary}]
Suppose $y$ is the longest boundary of $text[j{+}1..n]$ and $y \ne x''$; then $y$ is a suffix of $x$ and the occurrence of $y$ that starts at position $n{-}|x|{-}|y|{+}1$ overlaps the occurrence of $y$ that starts at position $j{+}1$. Thus, $text[1..n{-}1]$ contains a square. This is a contradiction.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{CatcherTime}]
The well-known algorithm that fills $b$ takes $O(n - j)$ time (see~\cite{Stringology}).

Denote $t = j - i + 1$. Suppose there exists a positive integer $n'$ such that our algorithm had computed a nonzero value of $s$ when $text$ had the length $n'$. Let $n_1 < \ldots < n_k$ be the set of all such integers. For each $l\in \overline{1,k}$, denote by $s_l$ the value of $s$ that had been computed when $text$ had the length $n_l$. We must prove that $\sum_{l=1}^k s_l = O(n - j)$.

Let $k'$ be the maximal integer such that $k'\in \overline{1,k}$ and $n_{k'} - b[n_{k'}] \le j + t$. Let us prove that $\sum_{l=1}^{k'} s_l = O(t)$. For any $l \in \overline{1,k'}$, denote $b_l = j + t - (n_l - b[n_l])$. Clearly for each $l \in \overline{1,k'}$, $b_l$ is the length of some boundary of $text[j{+}1..j{+}t]$. Denote $a_l = j + t - b_l$. Let us show that $s_l \ge a_l - a_{l-1}$ for at most one $l\in \overline{2,k'}$.

Suppose $s_{l_1} \ge a_{l_1} - a_{l_1-1}$ and $s_{l_2} \ge a_{l_2} - a_{l_2-1}$ for some $l_1$, $l_2$ such that $2\le l_1 < l_2 \le k'$. Since $text[1..n{-}1]$ does not contain squares, $b_{l} > 2b_{l+1}$ for all $l\in \overline{1,k'{-}1}$. Therefore, $a_{l_1} - a_{l_1-1} > a_{l_2} - a_{l_2-1}$ and we have $text[a_{l_1}{-}(a_{l_2}{-}a_{l_2-1}){+}1 .. a_{l_1}] = text[a_{l_2-1}{+}1..a_{l_2}]$. But $text[a_{l_2-1}{+}1..a_{l_2}]$ is a prefix of $text[a_{l_1}{+}1..j{+}t]$ because $text[a_{l_1}{+}1..j{+}t]$ and $text[a_{l_2-1}{+}1..j{+}t]$ are boundaries of $text[j{+}1..j{+}t]$. So, we obtain a square and this is a contradiction. Thus, $\sum_{l=1}^{k'} s_l < 2t + \sum_{l=2}^{k'}(a_l - a_{l-1}) = O(t)$.

Let us prove that $n_l - j = 2b[n_l] + t$ for all $l\in \overline{k'{+}2,k}$. Suppose, to the contrary, $n_l - j < 2b[n_l] + t$ for some $l\in \overline{k'{+}2,k}$. Obviously, $b[n_l] \ne 0$ and $b[n_l] \ne b[n_l{-}1] + 1$. Hence, $text[n_l{-}b[n_l{-}1]..n_l{-}1]$ has a boundary of the length $b[n_l] - 1$. Since $text[1..n{-}1]$ does not contain squares, we have $b[n_l{-}1] > 2(b[n_l] - 1)$. From the definition of $k'$ it follows that $n_l{-}1 - b[n_l{-}1] > j + t$, i.e., $b[n_l{-}1] + t < n_l - 1 - j$. Finally, $2b[n_l] + t \le b[n_l{-}1] + 1 + t < n_l - 1 - j + 1 = n_l - j$ and this is a contradiction.

Now it is easy to see that for each $l\in \overline{k'{+}2,k{-}1}$, $2b[n_l] < b[n_{l+1}]$ and thus $n_l < n_{l+1} - b[n_{l+1}]$ because $text[n_l{-}b[n_l]{+}1..n_l]$ and $text[n_{l+1}{-}b[n_{l+1}]{+}1..n_{l+1}]$ cannot overlap. To estimate the sum $\sum_{l=k'+1}^k s_l$, we prove that if for some $l \in \overline{k'{+}2,k}$, $s_l \ge n_l - n_{l-2}$, then for at most one $l' \in \overline{k'{+}2,l{-}1}$, the same inequality $s_{l'} \ge n_l - n_{l-2}$ holds. Indeed, suppose for some $l\in \overline{k'{+}2,k}$, $s_l \ge n_l - n_{l-2}$ and there are $l_1, l_2 \in \overline{k'{+}2,l{-}1}$ such that $l_1 < l_2$ and $s_{l_1}, s_{l_2} \ge n_l - n_{l-2}$. Then $(n_{l_2} - b[n_{l_2}]) - (n_{l_1} - b[n_{l_1}]) > n_l - n_{l-2}$ since $text[1..n{-}1]$ does not contain squares. Clearly, $n_{l-1} - n_{l-2} > b[n_{l-1}]$ and $l_2 \le l{-}2$. Therefore, $n_{l-1} - j \ge (n_{l-1} - n_{l_2}) + ((n_{l_2}-b[n_{l_2}]) - (n_{l_1} - b[n_{l_1}])) + t > b[n_{l-1}] + (n_l - n_{l-2}) + t >2b[n_{l-1}] + t$. But it is impossible since $n_{l-1} - j \le 2b[n_{l-1}] + t$.

Now we can estimate the sum $\sum_{l=k'+1}^k s_l$. If for each $l\in \overline{k'{+}2,k}$, $s_l < n_l - n_{l-2}$, then $\sum_{l=k'+1}^k s_l < t + \sum_{l=k'+2}^k (n_l - n_{l-2}) = O(n - j)$. Let $l_1 < l_2 < \ldots < l_m$ be the set of all $l'\in \overline{k'{+}2,k}$ such that $s_{l'} \ge n_{l'} - n_{l'-2}$. Denote $r = \sum_{p=1}^m s_{l_p}$. From the above it follows that for at most one $p \in \overline{1,m{-}1}$, $s_{l_p} \ge n_{l_m} - n_{l_m-2}$. So, $r < (m-1)(n_{l_m} - n_{l_m-2}) + 2t$. In the same way we obtain that for at most one $p \in \overline{1,m{-}2}$, $s_{l_p} \ge n_{l_{m-1}} - n_{l_{m-1}-2}$. So, $r < (m - 2)(n_{l_{m-1}} - n_{l_{m-1}-2}) + 2(n_{l_m} - n_{l_m-2}) + 2t$. Further, for at most one $p \in \overline{1,m{-}3}$, $s_{l_p} \ge n_{l_{m-2}} - n_{l_{m-2}-2}$. So, $r < (m - 3)(n_{l_{m-2}} - n_{l_{m-2}-2}) + 2(n_{l_{m-1}} - n_{l_{m-1}-2}) + 2(n_{l_m} - n_{l_m-2}) + 2t$. This process leads to the inequality $r < 2\sum_{p=1}^m (n_{l_p} - n_{l_p-2}) + 2t = O(n - j)$. Finally, we have $\sum_{l=1}^k s_l = \sum_{l=1}^{k'} s_l + \sum_{l=k'+1}^k s_l = O(t) + O(n - j) + r = O(n - j)$.
\end{proof}


\end{document}
